package com.leetcode.贪心;

import java.util.Arrays;

/**
 * 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
 * 每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
 * 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，
 * 其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
 * @author LZF
 *
 */
public class L406根据身高重建队列 {
	public static void main(String[] args) {
		int[][] people = {{7,1},{4,4},{7,0},{5,0},{6,1},{5,2}};
		int[][] result = reconstructQueue(people);
		Arrays.stream(result).forEach(a -> {System.out.print(Arrays.toString(a));});
	}
	/**
	 * 按照身高h来排序，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
	 * 此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！
	 * 那么只需要按照k为下标重新插入队列就可以了，
	 * 例如：
	 * 身高从大到小排序（身高相同k小的站前面）
	 * [7, 0][7, 1][6, 1][5, 0][5, 2][4, 4]
	 * 
	 * [5, 2]前面一定都比[5, 2]高，那么[5, 2]可以放心的插入下标为2的位置，这样就确定了[5, 2]前面一定有两个比它高
	 */
	public static int[][] reconstructQueue(int[][] people) {
		Arrays.sort(people,(o1,o2) -> {
			if(o1[0] == o2[0]) return Integer.compare(o1[1],o2[1]);
			else return -Integer.compare(o1[0],o2[0]);
		});
		Arrays.stream(people).forEach(a -> {System.out.print(Arrays.toString(a));});
		for(int i = 1;i < people.length;i++) {
			int[] temp = people[i];
			int end = people[i][1];
			for(int j = i;j > end;j--) {
				people[j] = people[j - 1];
			}
			people[end] = temp;
		}
		return people;
	}
}
